
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    /**
     * 第一遍
     * @param matrix
     * @param target
     * @return
     */
//    public boolean findNumberIn2DArray(int[][] matrix, int target) {
//        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
//            return false;
//        }
//        // 初始化m为二维数组的行数，n为二维数组的列数
//        int m = matrix.length, n = matrix[0].length;
//        // 初始化在右上角，右上角为第一行，最后一列；
//        int i = 0, j = n - 1;
//        while (i < m && j >= 0) {
//            if (matrix[i][j] == target){
//                return true;
//            }
//            // 从右上角开始，需要增大时，向下移动；需要减小时，向左移动；
//            if (matrix[i][j] < target) {
//                // 需要增大一点；改变行数，i++
//                i++;
//            } else {
//                // 需要减小一点;改变列数，j--
//                j--;
//            }
//        }
//        return false;
//    }










    /**
     * 第二遍
     * @param matrix
     * @param target
     * @return
     */
/*    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int m = matrix.length, n = matrix[0].length;

        int i = 0, j = n - 1;
        while (i < m && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            }
            if (matrix[i][j] > target) {
                j--;
            } else if (matrix[i][j] < target) {
                i++;
            }
        }
        return false;
    }*/


    /**
     * 第三遍 3/1
     * @param matrix
     * @param target
     * @return
     */
//    public boolean findNumberIn2DArray(int[][] matrix, int target) {
//        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
//
//        int m = matrix.length, n = matrix[0].length;
//        int i = 0, j = n - 1;
//        while (i < m && j >= 0) {
//            if (matrix[i][j] == target) {
//                return true;
//            } else if (matrix[i][j] < target) {
//                i++;
//            } else {
//                j--;
//            }
//        }
//        return false;
//    }


    /**
     * 第四遍 3/7
     * @param matrix
     * @param target
     * @return
     */
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;

        int m = matrix.length, n = matrix[0].length;
        int i = 0, j = n - 1;
        while (i < m && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] < target) {
                i++;
            } else {
                j--;
            }
        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
